package singlelist;

public class MySingleList {

     static class ListNode{
         public int val;
         public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }

    public ListNode head;

     public void createList(){
         ListNode node1 = new ListNode(12);
         ListNode node2 = new ListNode(23);
         ListNode node3 = new ListNode(34);
         ListNode node4 = new ListNode(45);
         ListNode node5 = new ListNode(56);

         node1.next = node2;
         node2.next = node3;
         node3.next = node4;
         node4.next = node5;

         this.head = node1;
     }

     //打印链表
     public void display() {
         ListNode cur = head;
         while(cur != null){
             System.out.print(cur.val+" ");
             cur = cur.next;
         }
         System.out.println();
     }

    /**
     * 从指定位置开始打印
     * @param newHead
     */
    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

     //计算链表的长度
     public int size() {
         int count = 0;
         ListNode cur = head;
         while(cur != null) {
             count++;
             cur = cur.next;
         }
         return count;
     }

     //判断链表中是否存在这个关键字
     public boolean contains(int key) {
         ListNode cur = head;
         while(cur != null){
             if(cur.val == key){
                 return true;
             }
             cur = cur.next;
         }
         return false;
     }

     //头插法
     public void addFirst(int data){
         ListNode node = new ListNode(data);

         node.next = head;
         head = node;
     }

     //尾插法
    public void addLast(int data){
         ListNode node = new ListNode(data);

         if(head == null){
             head = node;
             return;
         }
         ListNode cur = head;
         while(cur.next != null) {
             cur = cur.next;
         }
         cur.next = node;
    }

    //找到下标的对应的前一个节点  默认index合法
    private ListNode PrevOfIndex(int index){
         ListNode cur = head;
         while(index - 1 > 0) {
             cur = cur.next;
             index--;
         }
         return cur;
    }

    //在任意位置插入一个节点
    public void addIndex(int index, int data){
         if(index < 0 || index > size()){
             System.out.println("index 不合法");
             return;
         }

         if(index == 0){
             addFirst(data);
             return;
         }
         if(index == size()){
             addLast(data);
             return;
         }
         ListNode node = new ListNode(data);
         //调用查找对应下标的前驱的方法
         ListNode cur = PrevOfIndex(index);
         node.next = cur.next;
         cur.next = node;
    }

    /**
     * 找到对应关键字的前一个节点  默认链表至少有两个节点
     * @param key
     * @return
     */
    private ListNode SearchPrev(int key) {
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现的关键字为key的节点
    public void remove(int key){
         if(head == null){
             return;
         }
         if(head.val == key){
             head = head.next;
             return;
         }
         //调用了封装的查找前驱的方法
         ListNode cur = SearchPrev(key);
         ListNode dev = cur.next;
         cur.next = dev.next;
    }

    /**
     * 删除所有值为key的节点
     * @param key
     */
    public void removeAllKey(int key){
        if(head == null){
            return;
        }
//        //调用了封装的查找前驱的方法
//        ListNode cur = SearchPrev(key);
//        ListNode dev = null;
//        while(cur != null){
//            dev = cur.next;
//            cur.next = dev.next;
//            cur = SearchPrev(key);
//        }

        //不调用了封装的查找前驱的方法
        //遍历一遍链表完成删除
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
            }else{
                prev = cur;
            }
            cur = cur.next;
        }
        //这段代码只能写在最后，
        //否则当头节点的值是key，后面还跟着多个key时，最后无法将头结点的key删除掉
        if(head.val == key){
            head = head.next;
        }
    }

    public void clear(){

        head = null;

//        if(head == null){
//            return;
//        }
//        if(head.next == null){
//            head = null;
//            return;
//        }
//        ListNode next = null;
//        while(head.next != null){
//            next = head.next;
//            head.next = null;
//            head = next;
//        }
//        head = null;
    }

    //反转链表
    public ListNode reverseList() {
        if(head == null){
            return null;
        }
        ListNode cur = head.next;

        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //查找链表的中间节点
    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //分割链表
    public ListNode partition(ListNode head, int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;

        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                //第一次插入
                if(bs == null){
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                //第一次插入
                if(as == null){
                    as = ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(be == null){
            return as;
        }
        be.next = as;
        if(ae != null){
            ae.next = null;
        }
        return bs;
    }

    //判断链表是否为回文结构
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //一、找到链表的中间节点
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //二、从链表的中间节点开始反转链表
        ListNode cur = slow;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //三、最后从前 从后遍历链表直到head和slow相遇
        while(A != slow){
            if(A.val != slow.val){
                return false;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }

    //判断链表是否有环
    public boolean hasCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}
